// 版权归Go作者所有。版权所有。
// 此源代码的使用受BSD样式的约束
// 可以在许可证文件中找到的许可证。

package ssa

import (
	"cmd/compile/internal/types"
	"container/heap"
	"sort"
)

const (
	ScorePhi = iota // 朝向街区的顶部
	ScoreArg
	ScoreNilCheck
	ScoreReadTuple
	ScoreVarDef
	ScoreMemory
	ScoreReadFlags
	ScoreDefault
	ScoreFlags
	ScoreControl // 朝向区块底部
)

type ValHeap struct {
	a     []*Value
	score []int8
}

func (h ValHeap) Len() int      { return len(h.a) }
func (h ValHeap) Swap(i, j int) { a := h.a; a[i], a[j] = a[j], a[i] }

func (h *ValHeap) Push(x interface{}) {
	// Push和Pop使用指针接收器，因为它们修改切片的长度，
	// 不仅仅是它的内容。
	v := x.(*Value)
	h.a = append(h.a, v)
}
func (h *ValHeap) Pop() interface{} {
	old := h.a
	n := len(old)
	x := old[n-1]
	h.a = old[0 : n-1]
	return x
}
func (h ValHeap) Less(i, j int) bool {
	x := h.a[i]
	y := h.a[j]
	sx := h.score[x.ID]
	sy := h.score[y.ID]
	if c := sx - sy; c != 0 {
		return c > 0 // 高分来得晚。
	}
	if x.Pos != y.Pos { // 支持订单行步进
		return x.Pos.After(y.Pos)
	}
	if x.Op != OpPhi {
		if c := len(x.Args) - len(y.Args); c != 0 {
			return c < 0 // 较小的args稍后出现
		}
	}
	if c := x.Uses - y.Uses; c != 0 {
		return c < 0 // 较小的使用时间较晚
	}
	// 这些比较相当随意。
	// 这里的目标是脸上的稳定
	// 编译器中其他地方不相关的更改。
	if c := x.AuxInt - y.AuxInt; c != 0 {
		return c > 0
	}
	if cmp := x.Type.Compare(y.Type); cmp != types.CMPeq {
		return cmp == types.CMPgt
	}
	return x.ID > y.ID
}

func (op Op) isLoweredGetClosurePtr() bool {
	switch op {
	case OpAMD64LoweredGetClosurePtr, OpPPC64LoweredGetClosurePtr, OpARMLoweredGetClosurePtr, OpARM64LoweredGetClosurePtr,
		Op386LoweredGetClosurePtr, OpMIPS64LoweredGetClosurePtr, OpS390XLoweredGetClosurePtr, OpMIPSLoweredGetClosurePtr,
		OpRISCV64LoweredGetClosurePtr, OpWasmLoweredGetClosurePtr:
		return true
	}
	return false
}

// 计划每个块中的值。此阶段返回后
// b.值的顺序很重要，并且是这些值的顺序
// 将显示在程序集输出中。目前，它产生了一个
// 使用优先级队列的合理有效调度。TODO（khr）：
// 更聪明地安排时间。
func schedule(f *Func) {
	// 对于每个值，它在块中使用的次数
	// 按尚未计划的值。
	uses := make([]int32, f.NumValues())

	// 可重用优先级队列
	priq := new(ValHeap)

	// 值的“优先级”
	score := make([]int8, f.NumValues())

	// 排程顺序。我们将此列表中的值按相反顺序排列。
	// 常量绑定允许对其进行堆栈分配。64是
	// 足以覆盖几乎所有的预约电话。
	order := make([]*Value, 0, 64)

	// 将mem值映射到下一个活动内存值
	nextMem := make([]*Value, f.NumValues())
	// 每个值的附加假装参数。用于强制加载/存储顺序。
	additionalArgs := make([][]*Value, f.NumValues())

	for _, b := range f.Blocks {
		// 计算分数。更大的数字被安排在靠近区块末端的位置。
		for _, v := range b.Values {
			switch {
			case v.Op.isLoweredGetClosurePtr():
				// 我们还尽早为GetLowerdClosurePTR评分，以确保
				// 上下文寄存器未被踩踏。GetLowedClosurePtr只应出现
				// 在没有phi函数的输入块中，因此没有
				// 这里的冲突或歧义。
				if b != f.Entry {
					f.Fatalf("LoweredGetClosurePtr appeared outside of entry block, b=%s", b.String())
				}
				score[v.ID] = ScorePhi
			case v.Op == OpAMD64LoweredNilCheck || v.Op == OpPPC64LoweredNilCheck ||
				v.Op == OpARMLoweredNilCheck || v.Op == OpARM64LoweredNilCheck ||
				v.Op == Op386LoweredNilCheck || v.Op == OpMIPS64LoweredNilCheck ||
				v.Op == OpS390XLoweredNilCheck || v.Op == OpMIPSLoweredNilCheck ||
				v.Op == OpRISCV64LoweredNilCheck || v.Op == OpWasmLoweredNilCheck:
				// 在从同一地址加载之前，必须先进行零检查。
				score[v.ID] = ScoreNilCheck
			case v.Op == OpPhi:
				// 我们先要所有的网络钓鱼。
				score[v.ID] = ScorePhi
			case v.Op == OpVarDef:
				// 下一步我们要所有的Vardef。
				score[v.ID] = ScoreVarDef
			case v.Op == OpArgIntReg || v.Op == OpArgFloatReg:
				// 必须尽早安排In register args，以确保
				// 上下文寄存器未被踩踏。它们只应出现在输入块中。
				if b != f.Entry {
					f.Fatalf("%s appeared outside of entry block, b=%s", v.Op, b.String())
				}
				score[v.ID] = ScorePhi
			case v.Op == OpArg:
				// 为了更好地调试，我们希望尽早获得所有参数。
				score[v.ID] = ScoreArg
			case v.Type.IsMemory():
				// 尽早安排商店。这往往会
				// 降低寄存器压力。这也有助于确保
				// VARDEF ops安排在相应LEA之前。
				score[v.ID] = ScoreMemory
			case v.Op == OpSelect0 || v.Op == OpSelect1 || v.Op == OpSelectN:
				// 计划读取元组部分的伪操作
				// 紧接着元组生成op之后，因为
				// 此值已存在。这也消除了它的缺点
				// 对元组另一部分的错误依赖。
				// 还确保元组不会溢出。
				score[v.ID] = ScoreReadTuple
			case v.Type.IsFlags() || v.Type.IsTuple() && v.Type.FieldType(1).IsFlags():
				// 尽可能晚地安排标志寄存器生成。
				// 这确保我们只有一个活动标志
				// 一次价值。
				score[v.ID] = ScoreFlags
			default:
				score[v.ID] = ScoreDefault
				// 如果我们正在读取标志，请提前计划以缩短标志的生命周期。
				for _, a := range v.Args {
					if a.Type.IsFlags() {
						score[v.ID] = ScoreReadFlags
					}
				}
			}
		}
	}

	for _, b := range f.Blocks {
		// 找到区块的连锁店。
		// 不同区块的连锁店相互覆盖，因此
		// 经过计算的连锁店仅适用于该街区。
		for _, v := range b.Values {
			if v.Op != OpPhi && v.Type.IsMemory() {
				for _, w := range v.Args {
					if w.Type.IsMemory() {
						nextMem[w.ID] = v
					}
				}
			}
		}

		// 计算机使用。
		for _, v := range b.Values {
			if v.Op == OpPhi {
				// 如果phi使用某个值，则不会导致
				// 调度边缘，因为该使用来自
				// 上一次迭代。
				continue
			}
			for _, w := range v.Args {
				if w.Block == b {
					uses[w.ID]++
				}
				// 任何负载必须在以下存储之前到达。
				if !v.Type.IsMemory() && w.Type.IsMemory() {
					// v是一个负载。
					s := nextMem[w.ID]
					if s == nil || s.Block != b {
						continue
					}
					additionalArgs[s.ID] = append(additionalArgs[s.ID], v)
					uses[v.ID]++
				}
			}
		}

		for _, c := range b.ControlValues() {
			// 强制在末尾计划控制值，
			// 除非它们是φ值（必须是第一个）。
			// OpArg也是第一位的——若它是寄存器分配的堆栈
			// 对于LoadReg，如果它是register，则无论如何都是从头开始的。
			if c.Op == OpPhi || c.Op == OpArg {
				continue
			}
			score[c.ID] = ScoreControl

			// 明细表值取决于末尾的控制值。
			// 这减少了寄存器溢出的数量。我们找不到
			// 依赖于控件的所有值，只有带
			// 直接依赖。这是更便宜的，在那里测试
			// 泄漏的数量没有差别。
			for _, v := range b.Values {
				if v.Op != OpPhi {
					for _, a := range v.Args {
						if a == c {
							score[v.ID] = ScoreControl
						}
					}
				}
			}

		}

		// 将事物放入优先级队列
		// 最后应该出现的值最少。
		priq.score = score
		priq.a = priq.a[:0]

		// 使用可调度值初始化优先级队列。
		for _, v := range b.Values {
			if uses[v.ID] == 0 {
				heap.Push(priq, v)
			}
		}

		// 计划最高优先级值，更新使用计数，重复。
		order = order[:0]
		tuples := make(map[ID][]*Value)
		for priq.Len() > 0 {
			// 查找最高优先级的可调度值。
			// 请注意，明细表是反向组装的。

			v := heap.Pop(priq).(*Value)

			// 将其添加到计划中。
			// 在我们准备好发出元组生成操作之前，不要发出元组读取操作。
			// TODO:如果对性能没有帮助，可以删除上面的ReadTuple分数
			switch {
			case v.Op == OpSelect0:
				if tuples[v.Args[0].ID] == nil {
					tuples[v.Args[0].ID] = make([]*Value, 2)
				}
				tuples[v.Args[0].ID][0] = v
			case v.Op == OpSelect1:
				if tuples[v.Args[0].ID] == nil {
					tuples[v.Args[0].ID] = make([]*Value, 2)
				}
				tuples[v.Args[0].ID][1] = v
			case v.Op == OpSelectN:
				if tuples[v.Args[0].ID] == nil {
					tuples[v.Args[0].ID] = make([]*Value, v.Args[0].Type.NumFields())
				}
				tuples[v.Args[0].ID][v.AuxInt] = v
			case v.Type.IsResults() && tuples[v.ID] != nil:
				tup := tuples[v.ID]
				for i := len(tup) - 1; i >= 0; i-- {
					if tup[i] != nil {
						order = append(order, tup[i])
					}
				}
				delete(tuples, v.ID)
				order = append(order, v)
			case v.Type.IsTuple() && tuples[v.ID] != nil:
				if tuples[v.ID][1] != nil {
					order = append(order, tuples[v.ID][1])
				}
				if tuples[v.ID][0] != nil {
					order = append(order, tuples[v.ID][0])
				}
				delete(tuples, v.ID)
				fallthrough
			default:
				order = append(order, v)
			}

			// 更新参数的使用计数。
			for _, w := range v.Args {
				if w.Block != b {
					continue
				}
				uses[w.ID]--
				if uses[w.ID] == 0 {
					// 所有使用已计划，w现在可计划。
					heap.Push(priq, w)
				}
			}
			for _, w := range additionalArgs[v.ID] {
				uses[w.ID]--
				if uses[w.ID] == 0 {
					// 所有使用已计划，w现在可计划。
					heap.Push(priq, w)
				}
			}
		}
		if len(order) != len(b.Values) {
			f.Fatalf("schedule does not include all values in block %s", b)
		}
		for i := 0; i < len(b.Values); i++ {
			b.Values[i] = order[len(b.Values)-1-i]
		}
	}

	f.scheduled = true
}

// storeOrder命令与存储有关的值。就是，
// 如果v可传递地依赖于存储s，则v在s之后排序，
// 否则，v在s之前排序。
// 具体来说，值的顺序如下
// 仓库1
// NilCheck这取决于store1
// 取决于store1的其他值
// 仓库2
// NilCheck这取决于store2
// 取决于store2的其他值
// ...
// 未定义非存储和非NilCheck值的顺序
// （不一定是依赖顺序）。这个应该便宜些
// 而不是像上面那样的一个完整的日程安排。
// 请注意，简单的依赖顺序不起作用：没有
// NilChecks和IsNonNil等值之间的依赖关系。
// 辅助数据结构作为参数传入，因此
// 它们可以在调用者中分配并重用。
// 此功能负责重置它们。
func storeOrder(values []*Value, sset *sparseSet, storeNumber []int32) []*Value {
	if len(values) == 0 {
		return values
	}

	f := values[0].Block.Func

	// 查找所有商店

	// 存储值的值的成员。
	// 常量绑定允许对其进行堆栈分配。64是
	// 足以覆盖几乎所有的storeOrder电话。
	stores := make([]*Value, 0, 64)
	hasNilCheck := false
	sset.clear() // sset是在其他值中使用的存储集
	for _, v := range values {
		if v.Type.IsMemory() {
			stores = append(stores, v)
			if v.Op == OpInitMem || v.Op == OpPhi {
				continue
			}
			sset.add(v.MemoryArg().ID) // 记录使用了v的内存参数
		}
		if v.Op == OpNilCheck {
			hasNilCheck = true
		}
	}
	if len(stores) == 0 || !hasNilCheck && f.pass.name == "nilcheckelim" {
		// 没有商店，订单无关紧要
		return values
	}

	// 查找最后一个存储，它是其他存储未使用的存储
	var last *Value
	for _, v := range stores {
		if !sset.contains(v.ID) {
			if last != nil {
				f.Fatalf("two stores live simultaneously: %v and %v", v, last)
			}
			last = v
		}
	}

	// 我们为每个值分配一个存储编号。商店号码是
	// 此值传递依赖的最新存储的索引。
	// 当前块中的第i个存储获取存储编号3*i。零
	// 检查是否根据第i个存储获取存储编号3*i+1。
	// 依赖于第i个存储的其他值获取存储编号3*i+2。
	// 特例：0——未分配，1或2——它所依赖的最新存储
	// 在上一个块中（或根本没有存储，例如值为Const）。
	// 首先，我们回溯连锁店，将编号分配给所有门店，
	// 然后按DFS顺序将数字分配给其他值。
	count := make([]int32, 3*(len(stores)+1))
	sset.clear() // 重用稀疏集以确保只将值推送到堆栈一次
	for n, w := len(stores), last; n > 0; n-- {
		storeNumber[w.ID] = int32(3 * n)
		count[3*n]++
		sset.add(w.ID)
		if w.Op == OpInitMem || w.Op == OpPhi {
			if n != 1 {
				f.Fatalf("store order is wrong: there are stores before %v", w)
			}
			break
		}
		w = w.MemoryArg()
	}
	var stack []*Value
	for _, v := range values {
		if sset.contains(v.ID) {
			// 在sset中，表示v是一个存储，或已推送到堆栈，或已分配存储编号
			continue
		}
		stack = append(stack, v)
		sset.add(v.ID)

		for len(stack) > 0 {
			w := stack[len(stack)-1]
			if storeNumber[w.ID] != 0 {
				stack = stack[:len(stack)-1]
				continue
			}
			if w.Op == OpPhi {
				// Phi值不依赖于当前块中的存储。
				// 尽早这样做可以避免依赖循环。
				storeNumber[w.ID] = 2
				count[2]++
				stack = stack[:len(stack)-1]
				continue
			}

			max := int32(0) // 最新商店依赖关系
			argsdone := true
			for _, a := range w.Args {
				if a.Block != w.Block {
					continue
				}
				if !sset.contains(a.ID) {
					stack = append(stack, a)
					sset.add(a.ID)
					argsdone = false
					break
				}
				if storeNumber[a.ID]/3 > max {
					max = storeNumber[a.ID] / 3
				}
			}
			if !argsdone {
				continue
			}

			n := 3*max + 2
			if w.Op == OpNilCheck {
				n = 3*max + 1
			}
			storeNumber[w.ID] = n
			count[n]++
			stack = stack[:len(stack)-1]
		}
	}

	// 将计数转换为计数的前缀和：计数'[i]=sum_{j<=i}count[i]
	for i := range count {
		if i == 0 {
			continue
		}
		count[i] += count[i-1]
	}
	if count[len(count)-1] != int32(len(values)) {
		f.Fatalf("storeOrder: value is missing, total count = %d, values = %v", count[len(count)-1], values)
	}

	// 将值按所需的存储顺序放入计数索引箱中
	order := make([]*Value, len(values))
	for _, v := range values {
		s := storeNumber[v.ID]
		order[count[s-1]] = v
		count[s-1]++
	}

	// 订单为零检查源订单。我们希望第一个在源中触发。
	// 如果两个人在同一条线上，我们并不在乎哪一个先发生。
	// 见第18169期。
	if hasNilCheck {
		start := -1
		for i, v := range order {
			if v.Op == OpNilCheck {
				if start == -1 {
					start = i
				}
			} else {
				if start != -1 {
					sort.Sort(bySourcePos(order[start:i]))
					start = -1
				}
			}
		}
		if start != -1 {
			sort.Sort(bySourcePos(order[start:]))
		}
	}

	return order
}

type bySourcePos []*Value

func (s bySourcePos) Len() int           { return len(s) }
func (s bySourcePos) Swap(i, j int)      { s[i], s[j] = s[j], s[i] }
func (s bySourcePos) Less(i, j int) bool { return s[i].Pos.Before(s[j].Pos) }
